package code1.linkedlist;

/**
 * 原题链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
 */
public class P160 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
          val = x;
          next = null;
        }
    }

    //求两链表第一个相交的节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //求AB的长度差
        int lenA=0,lenB=0;
        ListNode pa=headA;
        ListNode pb=headB;
        while(pa!=null){
            pa=pa.next;
            lenA++;
        }
        while(pb!=null){
            pb=pb.next;
            lenB++;
        }
        //将AB对齐
        ListNode curA=headA;
        ListNode curB=headB;
        if(lenA>lenB){
            for(int i=0;i<lenA-lenB;i++){
                curA=curA.next;
            }
        }else{
            for(int i=0;i<lenB-lenA;i++){
                curB=curB.next;
            }
        }
        //curA和curB一同前进，直至找到二者值相等的节点
        while(curA!=null && curB!=null){
            if(curA.equals(curB)){      //注意是指针相等而不是值相等
                return curA;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }
}
